package arithmetic.LeetCode;

import java.util.HashMap;

import org.junit.jupiter.api.Test;

/**
 * @author jiangfeng on 2023/4/16
 */
public class LRUCache {

    public static void main(String[] args) {
        String[] a =new String[]{"put","put","put","put","put","get","put","get","get","put","get","put","put","put","get","put","get","get","get","get","put","put","get","get","get","put","put","get","put","get","put","get","get","get","put","put","put","get","put","get","get","put","put","get","put","put","put","put","get","put","put","get","put","put","get","put","put","put","put","put","get","put","put","get","put","get","get","get","put","get","get","put","put","put","put","get","put","put","put","put","get","get","get","put","put","put","get","put","put","put","get","put","put","put","get","get","get","put","put","put","put","get","put","put","put","put","put","put","put"};
        int[][] b=new int[][]{
                {10,13},{3,17},{6,11},{10,5},{9,10},{13},{2,19},{2},{3},{5,25},  //7
                {8},{9,22},{5,5},{1,30},{11},{9,12},{7},{5},{8},{9}, //4
                {4,30},{9,3},{9},{10},{10},{6,14},{3,1},{3},{10,11},{8}, //5
                {2,14},{1},{5},{4},{11,4},{12,24},{5,18},{13},{7,23},{8}, //5
                {12},{3,27},{2,12},{5},{2,9},{13,4},{8,18},{1,7},{6},{9,29}, //7
                {8,21},{5},{6,30},{1,12},{10},{4,15},{7,22},{11,26},{8,17},{9,29}, //8
                {5},{3,4},{11,30},{12},{4,29},{3},{9},{6},{3,4},{1},
                {10},{3,29},{10,28},{1,20},{11,13},{3},{3,12},{3,8},{10,9},{3,26},
                {8},{7},{5},{13,17},{2,27},{11,15},{12},{9,19},{2,15},{3,16},
                {1},{12,17},{9,1},{6,19},{4},{5},{5},{8,1},{11,7},{5,2},
                {9,28},{1},{2,2},{7,4},{4,22},{7,24},{9,26},{13,28},{11,26}};
        LRUCache obj = new LRUCache(10);
        for(int i=0;i<a.length;i++){
            if("put".equals(a[i])){
                obj.put(b[i][0],b[i][1]);
            }else {

                System.out.println(obj.get(b[i][0]));
            }
        }


        System.out.println(obj.get(1));
        obj.put(3,3);
        System.out.println(obj.get(2));
        obj.put(4,4);
        System.out.println(obj.get(1));
        System.out.println(obj.get(3));
        System.out.println(obj.get(4));
    }


    // 使用一个双向链表,(记录最新使用,链表可以o(1)增删),和一个hashMap(保证put,get都是o(1)).
    class Node {
        int val;
        int key;
        Node pre;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    class DNode{
        Node val;
        int key;
        DNode pre;
        DNode next;

        public DNode(int key,Node val){
            this.key =key;
            this.val =val;
        }
    }

    class ArrayMap{
        // 存的值是也是一个双项链表, 用拉链法解决hash冲突
        DNode[] values;
        public ArrayMap(int capacity){
            values=new DNode[capacity];
        }
        private int hash(int key){
            //如何解决hash冲突.
            // 暂时借用 TreadLocal里的map写法,直接下一个,开放寻址方式先放一下
            return key%values.length;
        }

        public Node get(int key){
            DNode d = get_(key);
            if(d==null){
                return null;
            }
            return d.key!=key?null:d.val;
        }
        
        

        private DNode get_(int key){
            DNode d = this.values[hash(key)];
            while(d!=null&&d.next!=null){
                if(d.key==key){
                    return d;
                }
                d = d.next;
            }
            // 没找到则给尾巴他
            return d;
        }

        public void put(int key,Node value){
            DNode d = get_(key);
            // 覆盖更新
            if(d!=null && d.key==key){
                d.val = value;
                return;
            }
            // 新增
            DNode nd = new DNode(key,value);
            if(d == null){
                this.values[hash(key)]=nd;
            }else{
                nd.pre=d;
                d.next=nd;
            }
        }


        public void remove(int key){
            DNode d = get_(key);
            // 删除不存在的元素.
            if(d==null){
                return;
            }
            //找到了
            if(d.key==key){
                DNode p = d.pre,n=d.next;
                if(p==null){
                    // 是头元素.
                    this.values[hash(key)]= n;
                }
                // 头尾接上.
                if(p!=null){
                    p.next=n;
                }
                if(n!=null){
                    n.pre=p;
                }
            }

        }
    }

    int capacity;
    int size;
    Node head;
    Node tail;
    //HashMap<Integer, Node> map;
    ArrayMap map;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new ArrayMap(capacity);
        this.size = 0;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        if (node == this.head) {
            return node.val;
        }
        // 删除链表
        deleteNode(node);
        // 放到头
        addHead(node);
        return node.val;
    }

    private void deleteNode(Node node) {
        if (node == this.tail) {
            this.tail = node.pre;
            // 注意: 删空了之后,head也要置空
            if (this.size == 1) {
                this.head = null;
            }
            //this.tail.next = null;
            return;
        }
        if (node == this.head) {
            this.head.next.pre = null;
            this.head = this.head.next;
            //this.head.pre=null;
            return;
        }
        Node preNode = node.pre;
        if (preNode != null) {
            preNode.next = node.next;
        }
        if(node.next!=null){
            node.next.pre = node.pre;
        }else {
            System.out.println("_"+node.key+","+ node.val);
        }
        node.next = null;
        node.pre = null;
    }

    private void addHead(Node node) {
        if (this.head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        this.head.pre = node;
        node.next = this.head;
        this.head = node;
    }

    public void put(int key, int value) {
        Node node = this.map.get(key);
        if (node != null) {
            if (node != head) {
                deleteNode(node);
                addHead(node);
            }
            // 注意: 更新下值
            node.val = value;
            // this.map.put(key,node);  // 这个不需要了,注释这个直接从44ms降到39 ms.直接击败从66%->99.42%
            return;
        }
        Node newNode = new Node(key, value);
        if (this.capacity == this.size) {
            // 注意: 这里传入key
            this.map.remove(this.tail.key);
            deleteNode(this.tail);
            this.size--;
        }
        addHead(newNode);
        this.size++;
        this.map.put(key, newNode);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */


